/**
 * @param {number[][]} pairs
 * @return {number}
 * 类似435 无重叠区间
 */
// 贪心解法,类似安排会议
var findLongestChain = function (pairs) {
    pairs.sort((a, b) => {
        return a[1] - b[1]
    })
    let count = 1,
        curr = pairs[0]
    for (let i = 1; i < pairs.length; i++) {
        if (pairs[i][0] > curr[1]) {
            count++
            curr = pairs[i]
        } else {
            continue
        }
    }
    return count
};

// dp解法
var findLongestChain2 = function (pairs) {
    pairs.sort((a, b) => {
        return a[1] - b[1]
    })
    const dp = new Array(pairs.length).fill(1)
    for (let i = 0; i < pairs.length; i++) {
        for (let j = 0; j < i; j++) {
            if (pairs[j][1] < pairs[i][0]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp)
};